#include <iostream>

using std::cout;
using std::endl;

int sort(int *arr, int i, int j)
{
    int val = arr[i], n = j;
    while(i < j){
        while(i < j && arr[j] < val)
            j--;
        if(i < j)
            arr[i++] = arr[j];

        while(i < j && arr[i] > val)
            i++;
        if(i < j)
            arr[j--] = arr[i];
        
    }
    arr[i] = val;
    for(int i{}; i <= j; i++){
        cout <<  arr[i] << " ";
    }
    cout << endl;
    return i;
}

void quickSort(int *arr, int begin, int end)
{
    if(begin >= end) return;
    int idx = sort(arr, begin, end);
    quickSort(arr, begin, idx - 1);
    quickSort(arr, idx + 1, end);
}

void resolve(int *arr, int begin, int end, int k)
{
    int idx = sort(arr, begin, end);    
    if(idx == k - 1){
        return ;
    }else if(idx > k - 1){
        resolve(arr, begin, idx - 1, k);
    }else{
        resolve(arr, idx + 1, end, k);
    }
    
}

int main(int args, char *argv[])
{
    int arr[] = {6, 7, 4, 0, 1, 5, 9};
    int len = sizeof(arr) / sizeof(int);
    // quickSort(arr, 0, len - 1);
    resolve(arr, 0, len - 1, 2);
    for(int i{}; i < len; i++){
        cout <<  arr[i] << " ";
    }
    cout << endl;
    return 0;
}